moddbfandomcom-20200213-history
Physics:2D Physics Engine:Intersection Detection
The following article is part of a series: Intersection Detection versus Collision Detection Before progressing any further I'd like to share the difference between intersection detection and collision detection. An intersection test will tell you if two shapes or objects are interpenetrating at a given time. On the other hand a collision test will tell you if two objects will collide over a period of time. A common example of a wrongly-named collision detection algorithm is the case of two intersecting circles. The test is commonly described: :"Given two circles with a center at point P, with radius R, the circles are colliding if the sum of the radii are greater than the distance between the two circles." This is actually an intersection test, because it tests of the two circles are intersecting at their given positions. If the circles were not intersecting, but were moving towards each other very quickly, then they would be colliding. However, this test will not tell us that. Why is this important? It isn't, really. However, it is information that will keep you from wondering why somebodies 'collision test' doesn't work at high speeds. The Separating Axis Theorem The Separating Axis Theorem (referred to as SAT from now on) is a method to decide whether or not two convex polygons intersect. The SAT involves projecting the two polygons onto every axis of both polygons. If these projections intersect on all axes, then the polygons are intersecting. Procedure Look at the pictures. They are much easier to understand. For each edge vector of both polygons: Determine the separating axis. To compute the separating axis: Find the unit vector of the edge (vector of magnitude 1) Find the normal (perpendicular) of that unit vector For each polygon: Find the dot product between each point in that polygon and the separating axis The projection of that polygon onto the separating axis spans between the smallest of those projected points and the largest of them If the projections do not intersect, stop. That means the polygons are not intersecting. If step 2 was completed, the polygons must be intersecting. Implementation The following code is written in Python, but should be readable for users of other languages as well. It may look daunting, but just take it step by step. You can probably skip over the Vector class (it's fairly standard), but it's there for completeness. import math class Vector: """Basic vector implementation""" def __init__(self, x, y): self.x, self.y = x, y def dot(self, other): """Returns the dot product of self and other (Vector)""" return self.x*other.x + self.y*other.y def __add__(self, other): # overloads vec1+vec2 return Vector(self.x+other.x, self.y+other.y) def __neg__(self): # overloads -vec return Vector(-self.x, -self.y) def __sub__(self, other): # overloads vec1-vec2 return -other + self def __mul__(self, scalar): # overloads vec*scalar return Vector(self.x*scalar, self.y*scalar) __rmul__ = __mul__ # overloads scalar*vec def __div__(self, scalar): # overloads vec/scalar return 1.0/scalar * self def magnitude(self): return math.sqrt(self.x*self.x + self.y*self.y) def normalize(self): """Returns this vector's unit vector (vector of magnitude 1 in the same direction)""" inverse_magnitude = 1.0/self.magnitude() return Vector(self.x*inverse_magnitude, self.y*inverse_magnitude) def perpendicular(self): """Returns a vector perpendicular to self""" return Vector(-self.y, self.x) class Projection: """A projection (1d line segment)""" def __init__(self, min, max): self.min, self.max = min, max def intersects(self, other): """returns whether or not self and other intersect""" return self.max > other.min and other.max > self.min class Polygon: def __init__(self, points): """points is a list of Vectors""" self.points = points # Build a list of the edge vectors self.edges = [] for i in range(len(points)): # equal to Java's for(int i=0; i